
//leetcode submit region begin(Prohibit modification and deletion)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    /**
     * 第一遍
     * @param list1
     * @param list2
     * @return
     */
//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        // 虚拟头节点,p为dummy链表的指针
//        ListNode dummy = new ListNode(-1), p = dummy;
//        // p1为list1链表的指针；p2为list2链表的指针
//        ListNode p1 = list1, p2 = list2;
//
//        while (p1 != null && p2 != null) {
//            // 比较p1和p2两个指针
//            // 将值较小的节点接到p指针
//            if (p1.val > p2.val) {
//                // p1的值大，则将p2放p中，同时移动p2位置
//                p.next = p2;
//                p2 = p2.next;
//            } else {
//                // p2的值大，则将p1放p中，同时移动p1位置
//                p.next = p1;
//                p1 = p1.next;
//            }
//            p = p.next;
//        }
//
//        if (p1 != null) {
//            p.next = p1;
//        }
//        if (p2 != null) {
//            p.next = p2;
//        }
//        return dummy.next;
//    }

    /**
     * 第二遍
     * @param list1
     * @param list2
     * @return
     */
//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        // 虚拟头节点,p为dummy链表的指针
//        ListNode dummy = new ListNode(-1), p = dummy;
//        ListNode p1 = list1, p2 = list2;
//
//        while (p1 != null && p2 != null) {
//            // 比较p1和p2所指向的值
//            if (p1.val < p2.val) {
//                p.next = p1;
//                p1 = p1.next;
//            } else {
//                p.next = p2;
//                p2 = p2.next;
//            }
//            p = p.next;
//        }
//
//        if (p1 != null) {
//            p.next = p1;
//        }
//        if (p2 != null) {
//            p.next = p2;
//        }
//        return dummy.next;
//    }


    /**
     * 第三遍
     *
     * @param list1
     * @param list2
     * @return
     */
//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        // 虚拟头节点,p为dummy链表的指针
//        ListNode dummy = new ListNode(-1), p = dummy;
//        ListNode p1 = list1, p2 = list2;
//
//        while (p1 != null && p2 != null) {
//            if (p1.val < p2.val) {
//                p.next = p1;
//                p1 = p1.next;
//            } else {
//                p.next = p2;
//                p2 = p2.next;
//            }
//            p = p.next;
//        }
//        if (p1 != null) {
//            p.next = p1;
//        }
//        if (p2 != null) {
//            p.next = p2;
//        }
//        return dummy.next;
//    }


    /**
     * 第四遍 2/27
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 虚拟头节点,p为dummy链表的指针
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;

        ListNode p1 = list1;
        ListNode p2 = list2;

        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }

        // 这里不需要循环了，所以不要用while
        if (p1 != null) {
            p.next = p1;
        }

        if (p2 != null) {
            p.next = p2;
        }

        return dummy.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
